N=1000;
m1=19683;
m2=2314;
S=[1271975337,1298928177,994045313,915238791,1730745873,1540017603,713140237,1314841383,1486881751,678226389,1969868151,1732723599,1748893599,1445957803,886974969,1062960813,1864842821,1800820107,728644977,1406438853,1974902577,1269248861,1182403737,1280792493,1872839603,750709621,1528506279,1731654369,1176373791,847775241,903700907,1981332069,747487513,1688181629,748819083,979996887,1819908729,1519288347,1525674327,1250677503,1923281271,982864287,1202785009,1384405611,1164915729,1135964979,1338694803,1735141383,1565799049,843299081,1412199963,1799781161,708804513,1326372183,1866080971,1474079553,705488409,1822842209,1514313649,835314531,789115731,1499083767,1408151749,1375315443,1717322427,1653306891,1612948957,1251120999,1261091457,1680087517,1009612251,1828709681,1516329189,1281827819,1342520133,1262896707,1486176309,693871029,1930568711,1866140181,1368555831,906820039,674733669,1803862329,1709606331,734321223,1481958993,678054483,1443487389,1852969821,1957144027,1513957311,1074632751,1927288179,1994436009,1429927351,1535713863,1544780889,1265510621,905297067,1956331701,1030621563,1984153659,811124091,788856867,1053163577,1496431719,1409954057,1758130299,1862412759,826327767,1209772563,955432503,965529423,1600672831,1124320361,1699666389,1391725271,1952809479,860316519,1422900447,1632671107,1399744149,1699286209,854744509,1757749779,981822399,770894451,983668443,1003004599,1567298241,791440227,1346320637,1548563299,1838180439,1178745291,1464316333,993720551,1164907567,1588249683,1726704849,1825850067,1532489733,722604579,706656861,944465163,747551373,1809635337,1895600673,1460324413,964562871,903182337,1171517733,1542612789,907699941,1432780529,1175055417,883975371,1060914509,1750454361,1440132117,1994879247,788412231,1178371053,1680347833,860562123,1779402249,1325864457,1434856851,802384347,1352739259,1072366573,849593469,724922489,1217106559,901900401,911657511,1415863653,1900497579,962740161,1546708733,1170214323,1493399997,923249851,1735466067,1338990157,979061073,1546385901,1197903771,944089929,676394791,1726493193,1367404529,1561581137,1115135123,1474709409,689784833,861014643,762692143,1074566847,1121211177,680929551,1443322437,981419319,1891150309,1816858998,1173482433,1979369019,1222619001,1780185249,1788949977,947953467,1714893759,1614425287,1643590931,780434037,988716899,1141207218,726131537,1461015253,1807471097,1915175583,1042177881,1401338971,1103928663,1215960101,1808218161,809657829,1932478997,782040339,1140917499,1544261441,1443694431,1305105939,1946904579,1878474029,1642300137,1634850297,1964225619,1225012247,854560593,1045903571,816623217,864410907,1965044283,736598939,1734260211,690755589,1757393501,884163303,1031037333,1186558561,1868054481,1206080789,1738701011,841706583,1500263253,1848017187,1578397329,942684849,1246170463,1707707789,1133235729,1837579559,1787589651,974597391,1932839583,1366019883,1695161661,717052277,941669693,1102661907,1268438813,992613159,1773881127,1054193499,1324681643,1674592083,1924329591,740185749,1597214761,1539116973,686579889,978125201,1273312897,691080223,1010162421,1438233021,1992392439,1952809479,1092911481,1227664293,1301774571,1164038179,1846154229,1561033459,1796132799,1187303499,1175758497,1254300309,1478740673,1173693063,1672116291,1174075323,1032638301,1936268883,1077557917,1990526253,1027117989,685124669,1647130473,1495494657,1962532881,1333443843,1925253279,1893642381,838371957,1786964643,1395544383,1290615387,992487437,744349521,1463609243,1511944451,1558995051,1387772553,1053691983,1905886659,679538133,931856879,1490462481,1220583589,1907892873,1971361239,1939149477,904467807,732389607,942274647,1004548203,907228809,1722065363,1376324303,1693269441,1243381401,1634756493,1120993427,1747526619,1259018613,1426713669,937870389,1203500789,955583143,873354393,1934701383,1604923077,1072804151,1012242921,973456749,1735294833,854301249,1309044921,1750065483,837137673,1080712833,1711810827,1436761173,764088889,1121961473,692828343,720726141,756876537,1696845693,927111651,853002807,1010715261,1209343203,1975685301,797013247,1968446933,1547433477,766208477,1210632903,919011231,757607139,1152390663,1915220949,1014816503,1958721507,1139079273,1441835049,915707691,923415747,1001705589,859642811,1026164781,1925253279,1948203657,828670509,1684999627,708753819,1857042477,936300627,1081061627,1211895033,1622899731,1203433443,1025110323,1443218677,685994787,1349604261,1532134287,756285129,706752741,1430973783,1346250429,721623843,1532704221,1327067349,1298416209,1386135909,1430166909,1347846741,1357056017,1825932861,933048031,869441571,1549742659,1024949421,1579714503,953134233,947103793,1053330697,755294759,752618871,1481204799,896786593,1332912051,1799858211,771896901,1961356443,1741779129,959451567,1269047583,860456691,1712620521,1731572559,1915523877,1184674419,1118825321,962463087,1029663623,1318270959,1234039643,969604263,1361831089,764344601,775175589,830373639,1701605127,1455175251,1845778799,737745867,1037271773,1661916429,948388561,1015966779,1856982609,825826307,1965267903,884700087,1894012273,1393842633,1141108989,1077209151,750232401,876447799,1350696761,743237343,1017227803,1576410471,1796998851,1796232429,1455149859,1951425129,1098291717,1720062733,1465891587,1250504553,1030660929,939646737,1695245463,1822508019,1635716349,1756993157,1684798173,702068973,1855108989,668839671,1409500553,1719877983,1802628189,863461719,1226473233,1239118479,1189390353,1208343089,1373259803,1976052417,1607097267,1542719083,1429650899,1140222537,1366003077,1127314519,1623512889,934559487,1494275751,1699316009,1967726757,1092609069,1302404427,1629514527,728017777,1166499639,1601087057,1711716679,1319682097,956333547,1770548007,1749094489,1310622597,1148081817,1014524697,1079277939,1573077741,854856309,1540801683,734990667,1327377939,1974593073,1106487589,1018946393,1897197947,1452681567,1607648391,1610878557,1920692143,789585351,1245649869,1083197439,1589382567,1257524049,1064890861,1973691711,1840419549,1448097993,753828869,1930292907,1160556961,1666695169,1532577429,1322592721,1582148949,1670764077,1470145977,1306092339,1135144653,1864668901,1745351519,731833623,1924505343,1100410089,1927702809,1027352217,1880354143,1008670473,687256729,1602852057,1075113657,863663103,1408747581,1718660511,1250238863,1085146659,1112699673,1118714819,1108833633,1193177331,1818654039,1773969741,807917337,699172119,1137095217,1420581159,1513670467,986196951,1045151883,728272371,1619289351,1605232513,1472335551,1029307589,937382337,1322682291,1996904583,722441103,1092376039,1245481191,1090064223,863003919,940922651,716659763,1840453581,732299199,1396788537,691478127,772744909,1134953709,820485459,1416799539,1047558537,1144025079,1690938747,1209046329,1304204557,748878379,672602187,1193064219,1083643191,870126381,833092059,787867293,838224507,812874477,1945133109,906330303,695774367,1266921567,1841063853,1481322483,1375129071,1654393071,1627004727,1197612891,1755782649,687533391,866703987,804385161,1875481857,1462456323,1189140219,813860357,1852565283,1684343979,1831906073,1927250991,827236659,876518253,1876772217,1634523489,1231349103,1171382391,1414440063,1029828977,888620947,1338907509,1279335951,1295751573,1822916661,1292686027,1243675861,1573683117,1047031299,696640419,1137406493,1822306011,1000379053,715545269,1128002517,1353737691,808201971,799523397,1455389919,987545619,1776207833,1527076203,1446498541,962796777,762359993,1306209279,1125454257,738198933,805363137,1248473007,1337046507,1281343617,813833109,814346433,905923737,1317639069,1748860461,1347573693,1937378007,1553613141,1304381599,1146507629,1352136033,1443903759,843866489,755191699,1132261859,780717599,1366489739,1151514549,1628458371,1820170907,1868552893,1889823879,1022052429,1790693897,1735525241,942680919,819203289,1398428301,1771922709,1437587271,1807803741,885026007,1931020257,1001694949,1841478313,1545534827,1806842953,1380278327,1570371169,911146323,1525143159,1649719059,1045743871,1916683437,774781929,1395544383,915425131,765405181,1841023091,1206561789,1151043273,746849709,954448353,1222817417,1461098733,1768036041,1125311193,1187267589,1636588287,1803070419,1495927683,1021077467,1979040747,703399419,801935903,1716592011,1785858273,953059689,990958593,730244139,1360901709,1909224927,1371727953,1721611737,1526559393,738671337,1207361277,1855033527,853532501,1573347099,1968949131,1545922503,1286459127,1098077419,949555953,905278581,1714939071,1049540329,1543792227,860640953,897581979,1354806459,955476933,1555567173,977683263,1254335983,826940691,688463631,1829600074,1874195577,1839753843,812714103,1136007357,1451168541,890628237,1108421991,699159843,1091583459,1139293907,1461914859,1555567173,745903299,1416678327,1973169221,1917853209,947726001,1760982907,1695740143,1858435851,1541038203,1899153621,1579633227,1586391039,1210485249,1082935253,1142814663,1178879103,885277413,873187209,1269081351,1612834569,1307034387,1914469257,1819319373,1318385169,712805607,886611303,1364450487,720882693,964840977,1012034333,755047233,1681676991,1508272263,888800823,1387949769,1287746151,1417212677,1157464783,1960052823,1745231463,1303022619,1440486477,1165883139,1540085751,1574477937,1247725053,826988401,1577710269,1939719231,1080299343,1633029459,1727025441,1066169061,685949189,1727240791,810959283,1913041149,1393221789,1448188977,714596121,1703034129,677783133,1808972589,778659183,1139770509,1271195907,1660528059,1543132593,1396807149,1254614103,1925048781,1393671843,1811636361,1773821799,1734475851,743936049,1447704333,1020131067,724142171,1000545939,836977641,682353951,1199006157,755946693,1971667629,763080777,718155987,1204563771,1789552341,827818347,1215277389,867747607,1816712699,1958555393,753188283,1717440003,1951636639,1868521287,1450127907,1136420163,1896043707,1146995657,703769229,1287098847,961526261,1461935817,1397008527,1302602243,1932296469,1157043621,1620341517,872449849,695235771,1302937047,1598001953,1872661149,840414793,1379487519,1031133321,1772906859,1539560277,1968884117,1329326017,760751361,768912489,1139941389,1135492587,839436219,1959304869,969094961,841102629,1018152099,1801698771,1827141299,836373201,1160409321,1813221141,1964126253,716436569,1394205951,1034168097,1051209981,1733623519,1849569973,1137105059,1577579049,1805942673,1321300107,1359815999,1754745913,946810373,743905161,876960573,1158369867,956603343,1461622563,1528703307,1939633363,1964890691,1459929963,710440677,1412985897,1067306217,1098266199,1361967303,1867700187,1420070319,769066677,981839329,902423321,1358173491,1194076393,873806607,1633390541,848830509,1089977127,979911351,1360279813,1921602271,1633978197,1420713513,1390167213,875657529,1368913181,1593841857,1798820703,924306093,993929427,1716285611,675382779,1532099677,1646121159,1027706541];